//题目:
// 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
// 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
// 区域：连接所有 '0' 的单元格来形成一个区域。
// 围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。
// 通过将输入矩阵 board 中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。
#include<iostream>
#include<queue>
#include<unordered_map>

using namespace std;
//代码:
class Solution 
{
    //1.确定上、下、左、右四个方向
    int arr_x[4]={-1,1,0,0};
    int arr_y[4]={0,0,-1,1};
public:
    void my_abs(vector<vector<char>>& board,int i,int j)
    {
        if(i==0 || j==0 || i==board.size()-1 || j==board[0].size()-1)return;
        //a.创建一个容器，存放所有符合条件的区域坐标
        vector<pair<int,int>> v_pir;
        //b.找到与(i，j)相连的区域
        queue<pair<int,int>> q;
        q.push(make_pair(i,j));
        board[i][j]='X';
        v_pir.push_back(make_pair(i,j));
        while(!q.empty())
        {
            pair<int,int> pir=q.front();
            q.pop();
            //c.判断(i,j)上下左右四周是否有相连的'O'区域
            for(int i=0;i<4;i++)
            {
                int x=pir.first+arr_x[i],y=pir.second+arr_y[i];
                if(x>=0 && x<board.size() && y>=0 && y<board[0].size() && board[x][y]=='O')
                {
                    if(x==0 || y==0 || x==board.size()-1 || y==board[0].size()-1)
                    {
                        //说明这块区域是不符合条件的，将v_pir中的元素改回来
                        for(const auto& pir:v_pir)
                            board[pir.first][pir.second]='O';
                        return;
                    }
                    q.push(make_pair(x,y));
                    board[x][y]='X';
                    v_pir.push_back(make_pair(x,y));
                }
            }
        }
    }
    void solve(vector<vector<char>>& board) 
    {
        //2.确定所有“被包围的区域”
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                if(board[i][j]=='O')
                {
                    my_abs(board,i,j);
                }
            }
        }
    }
};